package william.tree;

/**
 * @author ZhangShenao
 * @date 2024/3/23
 * @description <a href="https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 */
public class Leetcode108_将有序数组转换为二叉搜索树 {
    private class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 采用递归算法实现
     * 对于数组nums[l,r]范围,每次选取中间值nums[mid]作为树的根节点,nums[l,mid-1]范围内的元素作为左子树,nums[mid+1,r]范围作为右子树,构成一棵二叉搜索树
     * 因为每次左、右子树的节点数量都相同,所以最终的二叉搜索树一定是平衡的
     * <p>
     * 时间复杂度O(N) 需要遍历一次数组
     * 空间复杂度O(logN) 递归栈深度
     */
    public TreeNode sortedArrayToBST(int[] nums) {
        //边界条件校验
        if (nums == null || nums.length < 1) {
            return null;
        }

        //调用递归实现
        return sortedArrayToBSTRecursion(nums, 0, nums.length - 1);
    }

    /**
     * 递归实现
     * 将数组nums[l,r]范围构成一棵搜索二叉树
     */
    private TreeNode sortedArrayToBSTRecursion(int[] nums, int l, int r) {
        //递归终止条件
        if (l > r) {
            return null;
        }

        //找到数组的中间节点,作为二叉树的根节点
        int mid = l + ((r - l) >> 1);
        TreeNode root = new TreeNode(nums[mid]);

        //递归将[l,mid-1]范围作为左子树,[mid+1,r]范围作为右子树
        root.left = sortedArrayToBSTRecursion(nums, l, mid - 1);
        root.right = sortedArrayToBSTRecursion(nums, mid + 1, r);

        //返回根节点
        return root;
    }
}
